package mazeAssignment;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class UnweightedShortestSolve implements Solve
{
	private Maze maze;
	private Queue<Vertex> vertexQueue;
	private Map<Integer,Vertex> vertexMap;
	
	private boolean isSolved;
	
	
	public UnweightedShortestSolve()
	{
		maze = null;
		vertexQueue = null;
		vertexMap = null;
		isSolved = false;
	}
	
	
	@Override
	public void initialise(Maze m) throws SolveException
	{
		this.maze = m;
		this.vertexQueue = new LinkedList<Vertex>();
		this.vertexMap = new HashMap<Integer,Vertex>();
		
		generateGraphAndFindFirst();
	}

	@Override
	public void tick() throws SolveException
	{
		if(isSolved)
			throw new SolveException("UnweightedShortest.tick(): Already solved.");
		
		
		int mazeWidth = maze.getSizeX();
		
		Vertex currentVertex = vertexQueue.poll();
		
		int xPosition = currentVertex.number % mazeWidth;
		int yPosition = currentVertex.number / mazeWidth;
		
		MazeElement current = maze.getElement(xPosition, yPosition);
		
		//Check if we are at the end
		if(current.getSolveState() == MazeElement.SOLVE_END)
		{
			highLightValidPath(currentVertex.prev);
			isSolved = true;
			return;
		}
		
		//By default mark everything as invalid so
		//it is easier to mark the valid path in the end.
		current.markAsInvalid();
		
		for(Edge e : currentVertex.edges)
		{
			Vertex connectedVertex = e.dest;
			
			if(connectedVertex.weight == Double.MAX_VALUE)
			{
				connectedVertex.weight = currentVertex.weight + 1;
				connectedVertex.prev = currentVertex;
				vertexQueue.add(connectedVertex);
			}
		}
		
		if(vertexQueue.isEmpty())
			throw new SolveException("UnweightedShortest.tick(): No exit defined.");
	}
	
	/**
	 * Generates the graph for the unweighted shortest path algorithm.
	 */
	private void generateGraphAndFindFirst()
	{
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		for(int x = 0; x < xSize; x++)
		{
			for(int y = 0; y < ySize; y++)
			{
				//Generate an unique vertexNumber
				int vertexNumber = x + (y * xSize);
				Vertex currentVertex = new Vertex(vertexNumber);

				MazeElement current = maze.getElement(x, y);
				
				//If we find the begin vertex add it to the queue.
				if(current.getSolveState() == MazeElement.SOLVE_START)
				{
					currentVertex.weight = 0;
					vertexQueue.add( currentVertex );
				}

				//Connect with the vertex on the left
				if(x != 0 && ! current.getWest())
				{
					int leftNumber = (x - 1) + (y * xSize);
					Vertex leftVertex = vertexMap.get( leftNumber );
					
					//Connect current with left
					currentVertex.edges.add( new Edge(leftVertex, 1) );

					//Connect left with current
					leftVertex.edges.add( new Edge(currentVertex, 1) );
				}
				
				//Connect with the vertex above
				if(y != 0 && ! current.getNorth())
				{
					int northNumber = x + ((y - 1) * xSize);
					Vertex northVertex = vertexMap.get( northNumber );
					
					//Connect current with north
					currentVertex.edges.add( new Edge(northVertex, 1) );

					//Connect north with current
					northVertex.edges.add( new Edge(currentVertex, 1) );
				}
				
				//Insert vertex into the map
				vertexMap.put(vertexNumber, currentVertex);
			}
		}
	}
	
	/**
	 * Highlights the valid path from start to end.
	 */
	private void highLightValidPath(Vertex currentVertex)
	{
		while(true)
		{
			int mazeWidth = maze.getSizeX();
			
			int xPosition = currentVertex.number % mazeWidth;
			int yPosition = currentVertex.number / mazeWidth;
			
			MazeElement current = maze.getElement(xPosition, yPosition);
			
			if(current.getSolveState() == MazeElement.SOLVE_START)
			{
				return;
			}
			
			currentVertex = currentVertex.prev;
			
			//Mark as the valid path.
			current.visit();
		}
	}
	
	
	@Override
	public boolean isDone()
	{
		return isSolved;
	}
}
